package sword.chapter3String;

import java.util.ArrayList;
import java.util.List;

/**
 * 字符串中的所有变位词
 * 思路与s14一样
 * i - s1.length()是子字符串的前一个下标位置，子字符串开始位置是i - s1.length() + 1
 *
 * @author K
 * @date 2021-11-13 15:40
 */
public class S15FindAnagrams {
    public static void main(String[] args) {
        String s1 = "abc";
        String s2 = "cbadabacg";
        List<Integer> result = s15FindAnagrams(s1, s2);
        System.out.println();
    }

    public static List<Integer> s15FindAnagrams(String s1, String s2) {
        ArrayList<Integer> list = new ArrayList<>();
        if (s1.length() > s2.length()) {
            return list;
        }
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }
        if (checkAllZero(counts)) {
            list.add(0);
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++;
            if (checkAllZero(counts)) {
                list.add(i - s1.length() + 1);
            }
        }
        return list;
    }

    private static boolean checkAllZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}
